#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <string>
#include <vector>
#include <algorithm>

#include "Timer.h"

using namespace std;

int levenshteinCpp(const string &s1, const string &s2)
{
   int N1 = s1.size();
   int N2 = s2.size();
   int i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ ) {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; j++ ) {
         int upper = T[j+1];
         if ( s1[i] == s2[j] )
            T[j+1] = corner;
         else
            T[j+1] = min(T[j], min(upper, corner)) + 1;
         corner = upper;
      }
   }
   return T[N2];
}

int levenshteinC(const char* s1, const char* s2)
{
    int i, j, s1Len = strlen(s1), s2Len = strlen(s2), T[s2Len+1];

    for (i = 1; i <= s2Len; i++)
        T[i] = i;

    for (i = 0; i < s1Len; i++)
    {
        T[0] = i + 1;
        int c = i;
        for (j = 0; j < s2Len; j++)
        {
            int u = T[j+1];
			T[j+1]=s1[i]==s2[j]?c:(u<c?u<T[j]?u:c<T[j]?c:T[j]:c<T[j]?c:T[j])+1;
            c = u;
        }
    }
    return T[s2Len];
}

int compare (const void* a, const void* b)
{
	return strcmp(*(char**)a, *(char**)b);
}

int main ()
{
	int result = 0, word = 1, i = 0;
	char** names = (char**) malloc(5200 * sizeof(void*));

	// Read text file
	{
		names[0] = 0;
		names[word] = (char*) malloc(12);
		FILE* file = fopen("names.txt", "r");
		while (!feof(file))
		{
			char c = fgetc(file);

			if (c == '"')
				continue;

			if (c == ',')
			{
				names[word][i] = 0;
				i = 0;
				word++;
				names[word] = (char*) malloc(12);
			}
			else names[word][i++] = c;
		}
		fclose (file);
		names[word+1] = 0;
	}

	// Sort
	qsort(names+1, word, sizeof(char*), compare);

	// Levenshtein algorithm Test
	for (i = 2; names[i]; i++)
	{
		int levC = levenshteinC(names[i-1], names[i]);
		int levCpp = levenshteinCpp(names[i-1], names[i]);
		if (levC != levCpp)
			printf("ERROR: %s\t%u\t%u\n", names[i-1], levC, levCpp);
	}

	// Levenshtein speed Test
	Timer cppTimer, cTimer;

    cppTimer.start();
	for (i = 2; names[i]; i++)
		levenshteinCpp(names[i-1], names[i]);
	cppTimer.stop();

	cTimer.start();
	for (i = 2; names[i]; i++)
		levenshteinC(names[i-1], names[i]);
	cTimer.stop();

	printf("cpp: %f MicroSec.\nc:   %f MicroSec.\n", cppTimer.getElapsedTimeInMicroSec(), cTimer.getElapsedTimeInMicroSec());

	return 0;
}

